package com.yanyuan.algorithm.sort;

/**
 * @Description 桶排序
 * @Author yanyuan
 * @Date 16:17 2020/4/27
 * @Version 1.0
 **/
public class BucketSort {
    /**
     * @param arr
     * @param maxNum
     * @return
     */
    public static int[] sort(int[] arr, int maxNum) {
        //空桶数组+1
        int[] bucket = new int[maxNum+1];
        //实现算法
        for (int num : arr){
            bucket[num]++;
//            System.out.println(num + " \t " + bucket[num]);
        }
        printBucket(bucket);
        return bucket;
    }

    /**
     * 参与桶排序的值不能为负数
     * @param bucket
     */
    private static void printBucket(int[] bucket) {
        //定义变量
        int val;
        //桶的长度为10，i取值范围为0-9，取桶的下标值
        for (int i = 0; i < bucket.length; i++){
            val = bucket[i];//记录桶里面元素出现的次数：0-表示没有元素
//            System.out.println(val);
            for (int j = 1; j <= val ; j++){
                //val为出现次数， 为桶的下标
                System.out.println(i);
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{0, 1, 6, 2, 4, 1, 5, 19};
        int[] sortArr = sort(arr, 19);
//        for (int val : sortArr) {
//            if (val <= 0) {
//                continue;
//            }
//            System.out.print(" " + val);
//        }
    }
}
